
public class MySingleList implements ILinkedList{
    static class ListNode{
        //节点里的数据
        public int val;
        //存储下一个结点的地址
        public ListNode next;
        public ListNode(int val){
            this.val=val;
        }

    }
    //存储链表头节点的引用
    public ListNode head;
    public void createdList(){
        ListNode node1=new ListNode(11);
        ListNode node2=new ListNode(11);
        ListNode node3=new ListNode(11);
        ListNode node4=new ListNode(31);
        ListNode node5=new ListNode(58);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        head=node1;
    }
    @Override
    public void addFirst(int date) {
     ListNode node=new ListNode(date);
     node.next=head;
     head=node;
    }

    @Override
    public void addLast(int date) {
          ListNode node=new ListNode(date);
          //链表为空的情况，插入的节点就是第一个节点
        if(head==null){
            head=node;
            return;
        }
        //链表不为空的情况
          ListNode cur=this.head;
          while (cur.next!=null){
              cur=cur.next;
          }
          cur.next=node;
    }

    @Override
    public void addIndex(int index, int date) {
           checkPos(index);
           if(index==0){
               addFirst(date);
               return;
           }
           if(index==size()){
               addLast(date);
               return;
           }
           //中间位置的插入
           ListNode node=new ListNode(date);
           ListNode cur=findIndex(index);
        node.next=cur.next;
        cur.next=node;
    }
    private ListNode findIndex(int index){
        ListNode cur=this.head;
        int count=0;
        while (count!=index-1){
            count++;
            cur=cur.next;
        }
        return cur;
    }
    private void checkPos(int index){
        if(index<0||index>size()){
            throw new CheckPosException("index位置不合法"+index);
        }
    }

    @Override
    public boolean contains(int key) {
        ListNode cur=this.head;
        while (cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
       if(head==null){
           System.out.println("链表为空，无法进行删除");
           return;
       }
       //要删除的数字是头节点位置的数字
       if(head.val==key){
           head=head.next;
           return;
       }
       //要删除的数字是其他位置的数字
        ListNode cur=search(key);
       if(cur==null){
           System.out.println("没有你要删除的数字"+key);
       }
       ListNode del=cur.next;
       cur.next=del.next;

    }
    //寻找要删除的数字的前驱
     private ListNode search(int key) {
        ListNode cur=this.head;
        while (cur.next!=null){
            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
     }
    @Override
    public void removeAllKey(int key) {
        if(head==null){
            System.out.println("链表为空，没有你要删除的元素");
            return;
        }
        //判断除头节点之外的元素是否是我要删除的元素
        ListNode pre=head;
        ListNode cur=head.next;
        while (cur!=null){
            if(cur.val==key){
                pre.next=cur.next;
            }
            else {
                pre=cur;
            }
            cur=cur.next;
        }
        //单独判断头节点里的元素是否是我要删除的元素
        if(head.val==key){
            head=head.next;
        }
    }

    @Override
    public  int size() {
        int count=0;
        ListNode cur=this.head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
       //清空
    @Override
    public void clear() {
        ListNode cur=head;
        while (cur!=null){
            ListNode CUN=cur.next;
            cur.next=null;
            cur=CUN;
        }
        head=null;
    }

    @Override
    public void display() {
     ListNode cur=this.head; //链表从head开始进行打印
     while (cur!=null){
         System.out.print(cur.val+" ");
         cur=cur.next;
     }
        System.out.println();
    }
    public void display(ListNode newHead) {
        ListNode cur=newHead;//链表从newHead开始进行打印
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //翻转链表
    public ListNode reverseList() {
        //1.判断链表是不是为空，链表为空，直接返回null
        if(head==null){
            return null;
        }
        //2.判断是不是只有一个节点
        if(head.next==null){
            return head;
        }
        //上面两个if语句都没有进去，说明至少有两个及两个以上的节点
        ListNode cur=head.next;
        head.next=null;
        while (cur!=null){
            ListNode curN=cur.next;
            cur.next=head;
            head=cur;
            cur=curN;
        }
        return head;
    } //寻找中间节点
    public ListNode middleNode(){
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    //寻找倒数第k个节点
    public int kthToLast(int k){
        //1.判断k的合法性
       if(k<=0){
           return -1;
       }
       //2.先让fast走k-1步
        ListNode fast=head;
       ListNode slow=head;
       int count=0; //记录走的步数
        while (count!=k-1){
            fast=fast.next;
            if(fast==null){
                return -1;
            }
            count++;
        }
        //fast走完k-1步后，这时让fast,slow同时走，直到fast.next为空时，slow就是我们要找的倒数第k个节点
        while (fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow.val;
    }
  //合并两个链表，并要求合并之后的链表里的值是按照从小到大的顺序排列的
     public ListNode MergeTwoLinkedLists(ListNode headA, ListNode headB){
        ListNode newHead=new ListNode(-1);
        ListNode temp=newHead;
        while (headA!=null&&headB!=null){
            if(headA.val<headB.val){
                temp.next=headA;
                temp=headA;
                headA=headA.next;
            }
            else {
                temp.next=headB;
                temp=headB;
                headB=headB.next;
            }
        }
        if(headA!=null){
            temp.next=headA;
        }
        if(headB!=null){
            temp.next=headB;
        }
        return newHead.next;
     }
     //判断链表是不是回文序列
    public boolean chkPalindrome() {
        // write code here
        if(head == null) {
            return true;
        }
        //1.找中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.slow此时指向了中间位置 开始翻转后半部分
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }
        //3. 此时head和cur一直走 直到相遇
        while(head != slow) {
            if(head.val != slow.val) {
                return false;
            }
            //判断偶数的情况
            if(head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    public ListNode partition(ListNode pHead,int x){
        //先判断链表是否为空，如果链表为空，就返回null
        if (pHead==null){
            return null;
        }
        //走到这，证明链表不为空
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        ListNode cur=pHead; //让cur在头节点的位置，后续再移动
        while (cur!=null){
            if (cur.val<x){
                if (bs==null){
                    bs=be=cur;
                }
                else {
                    be.next=cur;
                    be=be.next;
                }
            }
            else {
                if (as==null){
                    as=ae=cur;
                }
                else {
                    ae.next=cur;
                    ae=ae.next;
                }
            }
            cur=cur.next;
        }
        if (bs==null){
            return as;
        }
        be.next=as;
        if (as!=null){
            ae.next=null;
        }
        return bs;
    }
        public boolean hasCycle(ListNode head) {
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
                if(fast==slow){
                    return true;
                }
            }
            return  false;
        }
        public void createLoop(){
         ListNode cur =head;
         while (cur.next!=null){
             cur=cur.next;
         }
         cur.next=head.next;
        }
    }




